package com.xsherl.leetcode.solution;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class SubstringWithConcatenation {

    /**
     * 双重循环，先统计words中字符串出现的次数
     * 依次判断子串是否在words中，如果有，则记录出现次数，
     * 如果出现次数大于words中字符串出现次数或者没有出现过，则说明子串不匹配
     *
     * @param s
     * 1 <= s.length <= 104
     * s 由小写英文字母组成
     * @param words
     * 1 <= words.length <= 5000
     * 1 <= words[i].length <= 30
     * words[i]由小写英文字母组成
     */
    public List<Integer> findSubstring(String s, String[] words) {
        HashMap<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            int count = wordMap.getOrDefault(word, 0);
            count++;
            wordMap.put(word, count);
        }
        int len = words.length, wordLen = words[0].length(), totalWordLen = wordLen * len;
        List<Integer> res = new ArrayList<>();
        HashMap<String, Integer> contains = new HashMap<>();
        for (int i = 0; i <= s.length() - totalWordLen; i++) {
            int clen = 0;
            for (int j = i; j < i + totalWordLen; j += wordLen) {
                String subString = s.substring(j, j + wordLen);
                int c = wordMap.getOrDefault(subString, 0);
                int cc = contains.getOrDefault(subString, 0);
                if (cc >= c || c == 0) {
                    break;
                }
                contains.put(subString, cc + 1);
                clen++;
                if (clen == len) {
                    res.add(i);
                    break;
                }
            }
            contains.clear();
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo","bar"};
        List<Integer> substring = new SubstringWithConcatenation().findSubstring(s, words);
        System.out.println(substring);
    }
}
